#include <vector>
#include <iostream>
#include <string>
#include <assert.h>

struct Node{
    std::string text;
    int freq;
    size_t index;
};

#define NIL {"NULL", 0}

class RangeTree{
public:

    Node max (Node a, Node b){
        if (a.freq > b.freq)
            return a;
        return b;
    }

    size_t getSize(size_t dataSize) {
        size_t newSize = 1;
        while (true) {
            if (newSize>=dataSize){
                return newSize;
            }
            assert(newSize < (INT_MAX-1)/2);
            newSize<<=1;
        }
        return 0;
    }
    
    std::vector<Node> tree;
    explicit RangeTree(std::vector<Node> &data){
        size_t size = getSize(data.size());
        tree.resize(2*size);
        for (size_t i = 0; i <= size + 1 - data.size(); ++i){
            data.push_back(NIL);
        }
        for (size_t i = 0; i < size; ++i){
            tree[size+i] = data[i];
        }
        for (size_t j = size - 1; j >= 1; --j){
            tree[j] = max(tree[2*j], tree[2*j+1]);
        }
    }
    RangeTree(){}
    
    Node rmq (size_t nodeIndex, size_t l, size_t r, size_t a, size_t b) {
        if (a == l && b == r)
            return tree[nodeIndex];
        size_t middle = (l + r) / 2;
        Node result = NIL;
        if (nodeIndex < tree.size()/2){
            result = max(rmq (nodeIndex*2, l, middle, a, std::min(b,middle)),
                         rmq (nodeIndex*2+1, middle+1, r, std::max(a,middle+1), b));
        }
        return result;
    }
    
    //ans = tree.rmq(1, 1, tree.size, a, b);//nodeIndex, l, r, a, b
    Node rmq (size_t a, size_t b){
        return rmq(1, 1, tree.size()/2, a, b);
    }
    
    void outTree(){
        for (size_t i = 1; i < tree.size(); ++i){
            std::cout << tree[i].text << " " << tree[i].freq << "\n";
        }
    }
    
};

